﻿namespace LeetCodeProject._0001_1000._001_100._81_90._085;

public class Solution
{
    public int MaximalRectangle(char[][] matrix)
    {
        int m = matrix.Length;
        if (m == 0)
        {
            return 0;
        }

        int n = matrix[0].Length;
        int[][] left = new int[m][];

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (matrix[i][j] == '1')
                {
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (matrix[i][j] == '0')
                {
                    continue;
                }

                int width = left[i][j];
                int area = width;
                for (int k = i - 1; k >= 0; k--)
                {
                    width = Math.Min(width, left[k][j]);
                    area = Math.Max(area, (i - k + 1) * width);
                }

                ret = Math.Max(ret, area);
            }
        }

        return ret;
    }
}